import java.util.*;

/**
 * @ClassName LRUCache
 * @Description TODO
 * @Author zheng
 * @Date 2022/3/11 16:58
 * @Version 1.0
 **/
public class LRUCache {
    int size;

    public LRUCache(int size) {
        this.size = size;
    }

    List<Integer> lst = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            //遍历数组，找到key对应的索引,删除，并在结尾处加上
            for (int i = 0; i < lst.size(); i++) {
                if (lst.get(i) == key) {
                    lst.remove(i);
                    break;
                }
            }
            lst.remove((Integer) key);
            lst.add(key);
            //更新map中数据
            map.put(key, value);
        } else {
            //情况分为两种
            //1、元素个数未满
            //将对应的数据，存到map中，并将数据插入list
            //2、元素个数满了，删除list头上的数据，并移除map中对应的元素
            if (lst.size() == size) {
                //移除最不经常访问的数据
                map.remove(lst.get(0));
                lst.remove(0);
            }
            lst.add(key);
            map.put(key, value);
        }
    }

    public Integer get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        int val = map.get(key);
        put(key, val);
        return val;
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(5);
        for (int i = 0; i < 10; i++) {
            lruCache.put(i, i);
            System.out.println(lruCache.lst.toString());
            lruCache.map.get(i);
            System.out.println(lruCache.lst.toString());
            //System.out.println(lruCache.map.get(i));
        }
    }
}
